1. Field of the Invention
The present invention relates to the design of lock-free data structures within computer systems. More specifically, the present invention relates to a method and apparatus for implementing a practical, lock-free doubly-linked list.
2. Related Art
Operations on linked lists become more complicated in a multi-threaded environment, because concurrently executing threads can potentially interfere with each other while accessing the same linked list. In order to prevent such interference, some systems use locks to prevent different threads from interfering with each other. Unfortunately, locks often cause processes to stall, which can lead to significant performance problems, especially in systems that support large numbers of concurrently executing processes.
Because of the performance problems that arise from locks, a number of researchers have developed “lock-free” data structures, such as linked lists, that operate efficiently in a multi-threaded environment. Harris describes a way to build and modify a lock-free linked list that can be constructed using only load-linked (LL)/store-conditional (SC) or compare-and-swap (CAS) instructions (see [Harris2001] Timothy L. Harris, “A Pragmatic Implementation of Non-Blocking Linked-Lists,” Proceedings of the 15th International Symposium on Distributed Computing, October 2001, pp. 300-14). Michael uses a variant of the Harris linked-list as the underlying structure for a lock-free hash table (see [Michael 2002] Maged M. Michael, “High Performance Dynamic Lock-Free Hash Tables and List-Based Sets,” The 14th Annual ACM Symposium on Parallel Algorithms and Architectures, pages 73-82, August 2002).
So far, none of these researchers have developed a lock-free doubly-linked list. A doubly-linked list is an important data structure for achieving computational efficiency in a diverse range of applications. A doubly-linked list allows searching in both forward and backward directions, and additionally allows insertion at any point and deletion at any point. Michael has developed a lock-free shared double-ended queue (see Maged M. Michael, “CAS-Based Lock-Free Algorithm for Shared Deques,” The Ninth Euro-Par Conference on Parallel Processing, LNCS volume 2790, pages 651-660, August 2003.). However, this double-ended queue does not support searching through the queue in both forward and backward directions, and does not support insertion or deletion at any point in the queue.
Hence, what is needed is a method and an apparatus for implementing a lock-free doubly-linked list.